#include <vector>
template <typename Comparable>

class BinaryHeap
{
private:
    // 堆的总长度
    int currentSize;
    // 对象向量（堆的物理形态）
    vector<Comparable> array;
    /* 初始化堆（实际上并不是建立新堆，而是下滤指定长度的空穴） */
    void buildHeap()
    { 
        // 从末尾节点的父节点开始，逐步将空穴下移（下滤）
        for(int i = currentSize/2; i>0; --i)
            percolateDown(i);
    }
    /* 下滤操作，参数是空穴序号 */
    void percolateDown(int hole);
    {
        int child;
        // 将（预定插入空穴处的值）先存储起来
        Comparable tmp = std::move(array[hole]);

        // 保证拥有子节点的情况下，每次将空穴移至子节点
        for(; hole * 2 <= currentSize; hole = child)
        {
            child = hole*2;
            // 寻找较小的子节点
            if(child != currentSize && array[child+1] < array[child])
                ++child;
            // 如果子节点比预定插入值更小，则将预定插入值引用到该子节点上，实现迭代操作
            if(array[child] < tmp)
                array[hole] = std::move(array[child]);
            else
                break;
        }
        // 最后寻找到空穴可以插入的地方，将原先预定插入的值放进去。
        array[hole] = std::move(tmp);
    }

public:
    explicit BinaryHeap(int capacity = 100)
    /* 使用items对象显式初始化函数，堆的currentSize被初始化为对象的items.size，堆的array的长度被初始化为对象的items.size + 10 */
    explicit BinaryHeap(const vector<Comparable> & items) : array(items.size() + 10), currentSize{items.size()}
    {
        // 逐个将堆节点赋值为对象保存的的节点信息
        for(int i = 0; i<items.size(); ++i)
            array[i+1] = items[i];
        // 内部方法，逐步用下滤空穴至指定位置
        buildHeap();
    }
    bool isEmpty() const
    const Comparable & findMin() const

    /*插入元素（允许重复）*/
    void insert (const Comparable & x)
    {
        //如果满了，则重新安排堆列
        if(currentSize == array.size() -1)
            array.resize(array.size() * 2);

        //当前节点的序号
        int hole = ++currentSize;   //b = ++a等价于 a=a+1 和 b=a，实际上是两个命令
        Comparable copy = x;
        array[0] = std::move(copy);

        //如果小于父节点，则把当前节点和父节点交换，若父节点再小于爷爷节点（一般只在未排序时发生），则再把父节点和爷爷节点交换，依次循环……
        for( ; x < array[hole/2]; hole /= 2) //C++中除法运算是向下取整的
            array[hole] = std::move(array[hole/2]);
        //最后把存储的当前节点值赋给最后赋值的祖宗节点，完成节点的交换
        array[hole] = std::move( array[0] );
    }
    /* 插入元素（右值引用） */
    void insert (Comparable && x)

    /* 删除最小元（无参数） */
    void deleteMin()
    {
        // 判空，若空则报错
        if(isEmpty())
            throw UnderflowException{};
        // 
        array[1] = std::move(array[currentSize--]);
        // 空穴下滤（内部方法）
        percolateDown(1);
    }
    /* 删除最小元（有参数） */
    void deleteMin( Comparable & minItem )
    {
        if(isEmpty())
            throw UnderflowException{};
        
        minItem = std::move(array[1]);
        array[1] = std::move(array[currentSize--]);
        // 空穴下滤（内部方法）
        percolateDown(1);
    }
    /* 下滤操作 */

    /*清空二叉堆*/
    void makeEmpty()
};